文本比较算法是一个经常会被使用到的算法。当然，大部分时间都是作为版本控制系统的命令来使用，比如 git diff。无论是提交前的差异性检查，还是多人合作时的分支合并，git diff 都是很合适且很有用的命令。相对而言，工程上需要实现一个文本比较算法比较少见。于个人而言，似乎只有在 14 年左右，有一个项目需要造轮子实现一个文本比较算法的变种。不过该算法更常出现的场景，是在面试环节，毕竟很少有人不使用 git diff / svn diff / shell diff，那么希望面试者曾今思考过这些命令是如何实现的也就是一件自然而然的事情（当然，真没用过就算了）。

本文对文本比较算法进行基本介绍，引入了一个基本模型对文本比较算法进行讨论，并将结合 git diff 的具体多个算法实现来介绍实践中文本比较算法。目录结构如下

1 文本比较算法和最小编辑距离

文本比较，如果用比较直观简单的话来解释，对于两个文本 A 和 B ，我们希望能找出他们之间的不同，并用某种方法来衡量不同的程度。这里的某种方法，一般是指编辑距离 D ——可以使用 D 个动作施加在 A 上，将其转换为 B ，动作包括插入 （insert）和 删除 （delete）（注 1），比如